//
// Created by TNJ on 2021/6/8.
//

#include <stdio.h>
#include "list_opt.h"

list_t *convert_list(list_t *list){
    if(list == NULL){
        return NULL;
    }

    list_t *head = list;  //新链表头结点
    list_t *temp = NULL;
    list = list->next;
    head->next = NULL;

    while(list != NULL){
        temp = list;  //保存遍历过的结点
        list = list->next;  //遍历下一个结点
        temp->next = head;  //头查法插入链表
        head = temp;  //更新链表头结点
    }

    return head;
}

list_t *get_last_k_node(list_t *list, int k){
    if(list == NULL || k <= 0){
        return NULL;
    }

    int index = 0;
    list_t *head = list;

    while(list != NULL){
        index++;
        list = list->next;
        if(index > k){
            //前一个指针已经移动了k个结点，则后一个指针开始移动
            //直到前一个指针已经移动到链表尾部，则后一个指针指向的就是倒数第k个结点
            head = head->next;
        }
    }

    //k值不正确，则找不到目标结点
    if(index < k){
        return NULL;
    }

    return head;
}

bool is_there_a_ring(list_t *list){
    if(list == NULL){
        return false;
    }

    list_t *node = list;
    while(list != NULL){
        if(list->next != NULL){
            list = list->next->next;  //首指针移动2个结点
            //两个指针相遇说明链表有环
            if(list == node){
                return true;
            }
        }else{
            break;
        }
        if(node != NULL){
            node = node->next;  //后面的指针移动一个结点
        }
    }

    return false;
}

list_t *transfer_to_ring_list(list_t *list){
    if(list == NULL){
        return NULL;
    }

    list_t *head = list;
    while(list->next != NULL){
        list = list->next;
    }
    list->next = head;

    return head;
}
